#pragma once

#include "stack"

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 给定一个整数数组 temperatures ，
 表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，
 下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。*
 输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]
 * */

//找到下一个大的就行啊 这种成为单调站
//通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
//
//时间复杂度为O(n)。

//其实就三点 如果当前元素大于原来的 top  就pop 原来的 然后计算当前下标和原来的差值 这个是while
//2 如果小于等于就入栈
//如果栈最后不null 就赋值为0
vector<int> dailyTemperatures(vector<int> &temperatures) {
    stack<int> s;//直接存idnex就行 获取值的时候根据下表去
    vector<int> res(temperatures.size(), 0);
    for (int i = 0; i < temperatures.size(); i++) {
        //如果为栈为null 就push 进去
        if (s.empty()) {
            s.push(i); ///
        } else {
            //如果temperatures[s.top()]>temperatures[i]  说明可以计算栈里面那个下标的差值了
            while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
                res[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);//pop完需要把这个加入进去的否则就少数了
        }
    }
    return res;
}

//暴力接法
vector<int> dailyTemperatures1(vector<int> &temperatures) {
    vector<int> res(temperatures.size(), 0);
    /**
     * temperatures = [73,74,75,71,69,72,76,73]
       输出: [1,1,4,2,1,1,0,0]
     * */
    for (int i = 0; i < temperatures.size(); i++) {

    }
    return res;
}